/* ****************************************************************************
 *
 * Copyright (c) Microsoft Corporation. 
 *
 * This source code is subject to terms and conditions of the Microsoft Public License. A 
 * copy of the license can be found in the License.html file at the root of this distribution. If 
 * you cannot locate the  Microsoft Public License, please send an email to 
 * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound 
 * by the terms of the Microsoft Public License.
 *
 * You must not remove this notice, or any other, from this software.
 *
 * THIS CODE AND INFORMATION ARE PROVIDED "AS IS" WITHOUT WARRANTY OF ANY
 * KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A
 * PARTICULAR PURPOSE.
 * ***************************************************************************/


#if !defined(AFX_DELAUNAY_H__C909E909_83C7_4FC2_BCD1_04F48E889084__INCLUDED_)
#define AFX_DELAUNAY_H__C909E909_83C7_4FC2_BCD1_04F48E889084__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <list>
#include <vector>
#include <map>
namespace delaunay
{

#define DEL_TOLERANCE std::numeric_limits<float>::denorm_min()*10

template<class T> class TTriangle;
template<class T> class TDelaunayMesher;

// class vertex
template<class T>
class TVertex
{
public:
	TVertex(){ m_ID=0; m_nbr=0; m_x=0; m_y=0;};
	TVertex(unsigned long ID, T _x, T _y, T _z=0): m_ID(ID), m_x(_x),m_y(_y)
	{	m_nbr=m_curNbr++;};
	TVertex(const TVertex<T>& v) {	m_ID=v.m_ID; m_nbr=v.m_nbr; m_x=v.m_x; m_y=v.m_y;};
	TVertex& operator = (const TVertex<T>& v)
	{	
		if (&v!=this) 
		{ m_ID=v.m_ID; m_nbr=v.m_nbr; m_x=v.m_x; m_y=v.m_y;};
		return *this;
	};
	~TVertex(){};			
	
	bool operator == (const TVertex<T>& v) const {	return m_ID == v.m_ID;};
	bool operator != (const TVertex<T>& v) const {	return m_ID != v.m_ID;};
	bool operator < (const TVertex<T>& v) const {	return m_nbr<v.m_nbr;};
	bool operator > (const TVertex<T>& v) const {	return m_nbr>v.m_nbr;};
	bool operator <= (const TVertex<T>& v) const {	return m_nbr<=v.m_nbr;};
	bool operator >= (const TVertex<T>& v) const {	return m_nbr>=v.m_nbr;};

	double SqrDist(const TVertex<T>& v) const
	{	return (m_x-v.m_x)*(m_x-v.m_x) + (m_y-v.m_y)*(m_y-v.m_y);};

	friend class TTriangle<T>;
	friend class TDelaunayMesher<T>;
protected:
	T m_x;
	T m_y;
	unsigned long m_ID;
	unsigned long m_nbr;
private:
	static unsigned long m_curNbr;
};


template<class T>
unsigned long TVertex<T>::m_curNbr=1;

// circle
template<class T>
class TCircle
{
public:
    TCircle():m_r2(0){}
    TCircle(const TVertex<T>& v, T r): m_center(v)  {m_r2=r;};
	TCircle(const TCircle<T>& c)	{	m_center = c.m_center; m_r2 = c.m_r2;};
	TCircle& operator = (const TCircle<T>& c)	{	if (&c!=this){m_center = c.m_center; m_r2 = c.m_r2;}return *this;};
    ~TCircle(){};

	bool Inside(const TVertex<T>* v)
	{	return m_center.SqrDist(*v) <= m_r2*m_r2; };

protected:
    TVertex<T> m_center;
    T m_r2;
};

template<class T>
class TEdge
{
public:
	typedef std::list< TEdge<T> > EdgeList;

    TEdge() { sv=NULL; ev=NULL;}
    TEdge(TVertex<T>* A, TVertex<T>* B){	sv=A; ev=B;}
	TEdge(const TEdge<T>& e)	{	sv = e.sv;	ev = e.ev;};
	TEdge& operator = (const TEdge<T>& e)	{	if (&e!=this){	sv = e.sv;	ev = e.ev;} return *this;};
    ~TEdge() {}

	bool operator == (const TEdge<T>& e) const {	return ((*sv==*e.sv && *ev==*e.ev) || (*sv==*e.ev && *ev==*e.sv));}
	bool operator != (const TEdge<T>& e) const {	return ((*sv != *e.sv && *ev!=*e.ev) && (*sv != *e.ev && *ev!=*e.sv));}

	bool ComperseEdge(const TEdge<T>& u) const
	{ return ( ( (*sv == *u.ev) && (*ev == *u.sv)) || ((*sv == *u.sv) && (*ev == *u.ev)));};
	/*! \brief check is edge is in list
	This function returns true if the current edge isn't in
	the list listCommonSide. And if it returns false,the first
	element of this list will be the common edge.
	*/
	bool NotCommonSide(EdgeList& listCommonSide) const;
	
	friend class TTriangle<T>;
protected:
    TVertex<T>* sv;
	TVertex<T>* ev;
};

template<class T>
bool TEdge<T>::NotCommonSide(EdgeList &listCommonSide) const
{
	int r,i ;
	TEdge<T> cote2;
	r = listCommonSide.size();
	for (i=0;i<r;i++)
	{
		ASSERT(!listCommonSide.empty());
		cote2 = listCommonSide.front();
		if (ComperseEdge(cote2))
		{
			return false ;
		}
		else 
		{
			listCommonSide.push_back(cote2);
			listCommonSide.pop_front();
		}
	}
	return true;
}

template<class T>
class TTriangle
{
public:
	typedef std::list< TTriangle<T> > TriangleList;

	TTriangle() {	m_v0=NULL; m_v1=NULL; m_v2=NULL;};
	TTriangle(TVertex<T>* A, TVertex<T>* B, TVertex<T>* C)
	{	ASSERT(A); ASSERT(B); ASSERT(C);
		m_v0=A; m_v1=B; m_v2=C;
		m_e0=TEdge<T>(m_v0,m_v1); m_e1=TEdge<T>(m_v1,m_v2); m_e2=TEdge<T>(m_v2,m_v0);	CalcCircumCircle();	
	};
	TTriangle(TVertex<T>* ve, const TEdge<T>& G)
	{	ASSERT(ve); ASSERT(G.sv); ASSERT(G.ev);
		m_v0=ve; m_v1=G.sv; m_v2=G.ev; m_e0=TEdge<T>(m_v0,m_v1); m_e1=TEdge<T>(m_v1,m_v2); m_e2=TEdge<T>(m_v2,m_v0); CalcCircumCircle(); };
	TTriangle(TVertex<T>* A, TVertex<T>* B, TVertex<T>* C, const TEdge<T>& E, const TEdge<T>& F, const TEdge<T>& G)
		: m_e0(E),m_e1(F),m_e2(G)
	{	ASSERT(A); ASSERT(B); ASSERT(C);
		m_v0=A; m_v1=B; m_v2=C; CalcCircumCircle();};

	TTriangle(const TTriangle<T>& t)	
		: m_e0(t.m_e0), m_e1(t.m_e1), m_e2(t.m_e2), m_circle(t.m_circle)
	{	ASSERT(t.m_v0); ASSERT(t.m_v1); ASSERT(t.m_v2); m_v0=t.m_v0; m_v1=t.m_v1; m_v2=t.m_v2; };

	TTriangle& operator = (const TTriangle<T>& t)
	{	
		if( &t != this)
		{	m_v0 = t.m_v0; m_v1 = t.m_v1; m_v2 = t.m_v2; m_e0 = t.m_e0; m_e1 = t.m_e1; m_e2 = t.m_e2;  m_circle=t.m_circle;}
		return *this;
	};
	~TTriangle() {}

	
	/*! \brief 

	This function returns true if the point v is in the surface of the triangle
	or on one of his edges.
	*/
	bool InsideTriangle(const TVertex<T>* v);
	bool InsideTriangleCircumCircle(const TVertex<T>* v ) {	ASSERT(v); return m_circle.Inside(v);};

	friend class TDelaunayMesher<T>;
protected:

	/*! \brief Splitting triangle
	 This function splits the only triangle t that contains the point ve. It
	 returns the list temporary with the good triangles.
	*/
	void split1(TVertex<T>* ve, TriangleList &temporary);
	/*! \brief Splitting triangle
	This function splits the two triangles t that contains the point ve and the
	triangle tr2 that has  the point ve in his circumcircle .
	It returns the list temporary with the good triangles.
	*/
	void split2(TVertex<T>* ve,const TTriangle<T>& tr2,TriangleList &temporary);
	void splitn(TVertex<T>* ve, TriangleList &temporary);
	const TCircle<T>& GetCircumCircle()	{	return m_circle;};
	/*! \brief deletes triangles
	This function deletes all the triangles that contain the vertices of the 
	supertriangle. It returns the final list of triangle.
	*/
	void PointOfTriangle(TriangleList& listtriangle);
	//! This function returns the circumcircle of the triangle t.
	void CalcCircumCircle();
	/*! \brief  Edge to triangle
	
	This fonction transformes a triangle defined with only three vertices
	into a triangle with six fields: three vertices and three edges.
	*/
	static void GetTriangle(TriangleList& temporary3, const TEdge<T>& side);
	inline bool CommonPoint(const TTriangle<T>& t) const;
	bool CommonPoint(const TVertex<T>* v) const
	{	ASSERT(v); ASSERT(m_v0); ASSERT(m_v1); ASSERT(m_v2); 
		return ((*v==*m_v0) || (*v==*m_v1) || (*v==*m_v2));
	};
	bool NotCommonSide(typename TEdge<T>::EdgeList &l) const 
	{	
		return (m_e0.NotCommonSide(l) && m_e1.NotCommonSide(l) && m_e2.NotCommonSide(l));
	};

protected:
    TVertex<T>* m_v0;
	TVertex<T>* m_v1;
	TVertex<T>* m_v2;
	TEdge<T> m_e0;
	TEdge<T> m_e1;
	TEdge<T> m_e2;
	TCircle<T> m_circle;

};

template<class T>
void TTriangle<T>::GetTriangle(typename TTriangle<T>::TriangleList &temporary3, const TEdge<T>& side)
{
	int n,i;

	n = temporary3.size();
	TTriangle<T> tr2;	
	for(i=0;i<n;i++)
	{
		tr2=temporary3.front();
        if ( ! 
			( (side.ComperseEdge(tr2.m_e0)) || (side.ComperseEdge(tr2.m_e1)) || (side.ComperseEdge(tr2.m_e2)) )
		)
		{
			temporary3.push_back(tr2);
			temporary3.pop_front();
		}
	}
};

template<class T>
bool TTriangle<T>::InsideTriangle(const TVertex<T>* v) 
{
	static TVertex<T>* sv;
	static TVertex<T>* ev;
	static T dx, dy1, dy2,x;
	int Rcross=0;
	int Lcross=0;
	
	// first verification
	ASSERT(v);
	ASSERT(m_v0);
	ASSERT(m_v1);
	ASSERT(m_v2);

	sv=m_v0;
	ev=m_v1;
	   
	dx= ev->m_x-sv->m_x;
	dy1= ev->m_y-sv->m_y;
	dy2= v->m_y-sv->m_y;
	   
	if (dy1!=0)
	{
		   x=dx*dy2/dy1+sv->m_x;
		   
		   if ((sv->m_y>v->m_y)!=(ev->m_y>v->m_y))
		   {
			   if ((x-v->m_x)>DEL_TOLERANCE) 
				   Rcross++;
		   }
		   
		   if ((sv->m_y<v->m_y)!=(ev->m_y<v->m_y))
		   {
			   if ((x-v->m_x)<-DEL_TOLERANCE) 
				   Lcross++;
		   }
	}
	 // second verification
	   
	 sv= m_v1;
	 ev= m_v2;
	   
	 dx= ev->m_x-sv->m_x;
	 dy1= ev->m_y-sv->m_y;
	 dy2= v->m_y-sv->m_y;
	   
	 if (dy1!=0){
		   
		 x=dx*dy2/dy1+sv->m_x;
		   
		 if ((sv->m_y>v->m_y)!=(ev->m_y>v->m_y))
		 {
		  if ((x-v->m_x)>DEL_TOLERANCE)
			  Rcross++;
		 }
		   
		 if ((sv->m_y<v->m_y)!=(ev->m_y<v->m_y))
		 {
			   if ((x-v->m_x)<-DEL_TOLERANCE)
				   Lcross++;
		 }
	   }
	   
	   // third verification
	   
	   sv= m_v2;
	   ev= m_v0;
	   
	   dx= ev->m_x-sv->m_x;
	   dy1= ev->m_y-sv->m_y;
	   dy2= v->m_y-sv->m_y;
	   
	   if (dy1!=0){
		   x=dx*dy2/dy1+sv->m_x;
		   
		   if ((sv->m_y>v->m_y)!=(ev->m_y>v->m_y))
		   {
			   if ((x-v->m_x) > DEL_TOLERANCE)
				   Rcross++;
		   }
		   
		   if ((sv->m_y<v->m_y)!=(ev->m_y<v->m_y))
		   {
			   if ((x-v->m_x) < - DEL_TOLERANCE)
				   Lcross++;
		   }
	   }
	   
	   //conclusion..
	   if ( ((Rcross %2) != (Lcross %2)) || (Rcross %2 ) )
		   return true;
	   else 
		   return false;
	   
};

template<class T>
void TTriangle<T>::CalcCircumCircle()
{
	static TVertex<T>* A, *B, *C;
	static T distAB, distBC, distCA;
	static T r;
	static T BAx,CAy,BAy,CAx;
	
	TVertex<T> center;
	
	A = m_v0;
	B = m_v1;
	C = m_v2;
	
	BAx=(B->m_x-A->m_x);
	CAy=(C->m_y-A->m_y);
	BAy=(B->m_y-A->m_y);
	CAx=(C->m_x-A->m_x);
	
	distAB=sqrt(BAx*BAx+BAy*BAy);
	distBC=sqrt((C->m_x-B->m_x)*(C->m_x-B->m_x)+(C->m_y-B->m_y)*(C->m_y-B->m_y));
	distCA=sqrt(CAx*CAx+CAy*CAy);
	
	r=fabs((distAB)*(distBC)*(distCA)/(2*(BAx*CAy-CAx*BAy)));
	
	center.m_x=A->m_x-((BAy*distCA*distCA)-(CAy*distAB*distAB))/(2*(BAx*CAy-CAx*BAy));
	center.m_y=A->m_y+((BAx*distCA*distCA)-(CAx*distAB*distAB))/(2*(BAx*CAy-CAx*BAy));	
	
	m_circle=TCircle<T>(center,r);
};	

template<class T>
void TTriangle<T>::split1(TVertex<T>* ve, typename TTriangle<T>::TriangleList& temporary)
{
	ASSERT(ve->m_nbr>0);
	ASSERT(m_v0->m_nbr>0);
	ASSERT(m_v1->m_nbr>0);
	ASSERT(m_v2->m_nbr>0);

	TRACE(_T("Spli1\n"));

	TTriangle<T> t1(m_v0,m_v1,ve);
	TTriangle<T> t2(m_v1,m_v2,ve);
	TTriangle<T> t3(m_v2,m_v0,ve);

    temporary.push_front(t1);
    temporary.push_front(t2);
    temporary.push_front(t3);
};


template<class T>
void TTriangle<T>::split2(TVertex<T>* ve,const TTriangle<T>& tr2, typename TTriangle<T>::TriangleList &temporary)
{
    TVertex<T> *A,*B,*C;
    TVertex<T> *A2,*B2,*C2;
	TVertex<T> *a,*b,*c,*d;
    TEdge<T> u,v,w;
    TEdge<T> u2,v2,w2;


	ASSERT(ve->m_nbr>0);
	ASSERT(m_v0->m_nbr>0);
	ASSERT(m_v1->m_nbr>0);
	ASSERT(m_v2->m_nbr>0);

	TRACE(_T("Spli2\n"));
	
    A = m_v0;
    B = m_v1;
    C = m_v2;
	
    A2 = tr2.m_v0;
    B2 = tr2.m_v1;
    C2 = tr2.m_v2;
	
    u = m_e0;
    v = m_e1;
    w = m_e2;
	
    u2 = tr2.m_e0;
    v2 = tr2.m_e1;
    w2 = tr2.m_e2;
	
	if ((u==u2) || (u==v2) || (u==w2)) 
	{
		a = m_v0;
		b = m_v1;
	}
	
    else if ((v==u2) ||(v==v2) || (v==w2)) 
	{
		a = m_v1;
		b = m_v2;
	}
	else if ((w==u2) || (w==v2) || (w==w2))
	{
		a = m_v2;
		b = m_v0;
	}
	else
	{
		TRACE(_T("Warning! a,b not found\n"));
	}
	// we have a and b
	if ((*A != *a) && ( *A!= *b)) c = m_v0;
	else if ((*B != *a) && (*B != *b)) c = m_v1;
	else if ((*C != *a) && (*C != *b)) c = m_v2;
	else
	{
		TRACE(_T("Warning! c not found\n"));
	}
	
	if ((*A2 != *a) && (*A2 != *b)) d = tr2.m_v0;
	else if ((*B2 != *a) && (*B2 != *b)) d = tr2.m_v1;
	else if ((*C2 != *a) && (*C2 != *b)) d = tr2.m_v2;
	else
	{
		TRACE(_T("Warning! d not found\n"));
	}
	
	// Now, we have the 4 vertices of the 4-edges polygon
	// We construct the triangles and we copy them in the temporary list
	TTriangle<T> t1(c,a,ve);
	TTriangle<T> t2(a,d,ve);
	TTriangle<T> t3(d,b,ve);
	TTriangle<T> t4(b,c,ve);

    temporary.push_front(t1);
    temporary.push_front(t2);
    temporary.push_front(t3);
    temporary.push_front(t4);
};

template<class T>
void TTriangle<T>::splitn(TVertex<T>* ve, typename TTriangle<T>::TriangleList& temporary)
{
	TEdge<T>::EdgeList listCommonSide;
	TTriangle<T>::TriangleList temporary3;

	ASSERT(ve);
	ASSERT(m_v0);
	ASSERT(m_v1);
	ASSERT(m_v2);

	TRACE(_T("Splin\n"));

	TTriangle<T> tri;

	TTriangle<T> t1(m_v0,m_v1,ve);
	TTriangle<T> t2(m_v1,m_v2,ve);
	TTriangle<T> t3(m_v2,m_v0,ve);

    temporary3.push_front(t1);
    temporary3.push_front(t2);
    temporary3.push_front(t3);
	
    listCommonSide.push_front(m_e0);
    listCommonSide.push_front(m_e1);
    listCommonSide.push_front(m_e2);
	
    TEdge<T> side;

    while ( ! temporary.empty())
	{
		tri = temporary.front();

		if (tri.NotCommonSide(listCommonSide))
		{
			temporary3.push_back(tri);
			temporary.pop_front();	
		}
		else 
		{
			side=listCommonSide.front();
			
			listCommonSide.pop_front();			
			if (!side.ComperseEdge(tri.m_e0))
			{
				listCommonSide.push_front(tri.m_e0);
			}
			if (!side.ComperseEdge(tri.m_e1))
			{
				listCommonSide.push_front(tri.m_e1);
			}	
			if (!side.ComperseEdge(tri.m_e2))
			{
				listCommonSide.push_front(tri.m_e2);
			}		
			
			TVertex<T>* z;
			
			if ((*tri.m_v0 != *side.sv) && (*tri.m_v0 != *side.ev)) 
			{
				z = tri.m_v0;
			}
			else if ((*tri.m_v1 != *side.sv) && (*tri.m_v1 != *side.ev)) 
			{
				z = tri.m_v1;
			}
			else if ((*tri.m_v2 != *side.sv) && (*tri.m_v2 != *side.ev)) 
			{
				z = tri.m_v2;
			}
			else
			{
				TRACE(_T("Warning z not set !\n"));
			}

			ASSERT(z->m_nbr>0);
			
			TEdge<T> side2(ve,z);
			TEdge<T> side2bis(z,ve);
			
			ASSERT(side.sv->m_nbr>0);
			ASSERT(side.ev->m_nbr>0);
			ASSERT(side2.sv->m_nbr>0);
			ASSERT(side2.ev->m_nbr>0);
			ASSERT(side2bis.sv->m_nbr>0);
			ASSERT(side2bis.ev->m_nbr>0);

			TTriangle<T> triangle1(side.sv,side2);
			TTriangle<T> triangle2(side.ev,side2bis);
			
			tri=temporary3.front();
			GetTriangle(temporary3, side);
			tri=temporary3.front();
			
			temporary3.pop_front();
			temporary.pop_front();
	
			ASSERT(triangle1.m_v0->m_nbr>0);
			ASSERT(triangle1.m_v1->m_nbr>0);
			ASSERT(triangle1.m_v2->m_nbr>0);
			ASSERT(triangle2.m_v0->m_nbr>0);
			ASSERT(triangle2.m_v1->m_nbr>0);
			ASSERT(triangle2.m_v2->m_nbr>0);
			temporary3.push_front(triangle1);
			temporary3.push_front(triangle2);
		}
    }

	while(!temporary3.empty())
	{
		TTriangle<T> tri = temporary3.front();
		temporary.push_front(tri);
		temporary3.pop_front();
	}
};

template<class T>
void TTriangle<T>::PointOfTriangle(typename TTriangle<T>::TriangleList& lFaces)
{
	typename TTriangle<T>::TriangleList::iterator i;
	for (i = lFaces.begin(); i != lFaces.end();)
	{
		if ( CommonPoint(*i) )
		{
			i=lFaces.erase(i);
		}
		else
		{
			i++;
		}
	}
}


template<class T>
inline bool TTriangle<T>::CommonPoint(const TTriangle<T> &t) const
{
	return (*m_v0==*t.m_v0) || (*m_v0==*t.m_v1) || (*m_v0==*t.m_v2)
		|| (*m_v1==*t.m_v0) || (*m_v1==*t.m_v1) || (*m_v1==*t.m_v2)
		|| (*m_v2==*t.m_v0) || (*m_v2==*t.m_v1) || (*m_v2==*t.m_v2);
}

template<class T>
class TDelaunayMesher
{
public:
	typedef std::map<unsigned long, TVertex< T > > VertexContainer;

	TDelaunayMesher(){};
	~TDelaunayMesher(){};

	// Preparing meshing
	void AddVertex(const TVertex<T>& v) {	_ASSERT(v.m_ID>=0); m_lVertices[v.m_ID]=v;};
	// removing a vertice by index
	void RemoveVertex(unsigned long ID) { m_lVertices.erase(m_lVertices.find(ID));};
	//! remove a vertex by pointer
	typename VertexContainer::iterator RemoveVertex(TVertex<T>* v){ return m_lVertices.erase(m_lVertices.find(v->m_ID)); v=NULL;};
	//! remove all vertices
	void RemoveAllVertex()			{	m_lVertices.clear();};

	// meshing
	bool GenerateMesh();

	// retreiving info
	double GetMaxX() const		{	return m_maxx;};
	double GetMaxY() const		{	return m_maxy;};
	double GetMinX() const		{	return m_minx;};
	double GetMinY() const		{	return m_miny;};

	const VertexContainer& GetVertices() const			{	return m_lVertices;};
	VertexContainer& GetVertices()						{	return m_lVertices;};
	const typename TTriangle<T>::TriangleList& GetFaces() const	{	return m_lFaces;};
	typename TTriangle<T>::TriangleList& GetFaces()				{	return m_lFaces;};

protected:
	void GenerateSuperTriangles();
	void CleanSuperTriangles();

protected:
	VertexContainer m_lVertices;
	typename TTriangle<T>::TriangleList m_lFaces;
	TTriangle<T> m_triSuper;
	double m_minx, m_maxx, m_miny, m_maxy;
};

template<class T>
void TDelaunayMesher<T>::GenerateSuperTriangles()
{
	VertexContainer::iterator i;
	TVertex<T> v;

	unsigned long maxnbr;
	
	if( m_lVertices.size()==0)
		return;

	i = m_lVertices.begin();
	v=i->second;
	m_maxx=v.m_x;		m_maxy=v.m_y;
	m_minx=v.m_x;		m_miny=v.m_y;
	maxnbr=v.m_nbr;
	i++; 
	for (; i != m_lVertices.end(); i++)
	{
		v=i->second;

		maxnbr=__max(maxnbr, v.m_nbr);
		m_maxx=__max(m_maxx, v.m_x);
		m_maxy=__max(m_maxy, v.m_y);
		m_minx=__min(m_minx, v.m_x);
		m_miny=__min(m_miny, v.m_y);
	}

	// constuction of the super triangle  	
	T dx=m_maxx-m_minx;
	T dy=m_maxy-m_miny;

	TVertex<T> ll(maxnbr+1,m_minx-5*dx,m_miny-5*dy);
	TVertex<T> lr(maxnbr+2,m_maxx+5*dx,m_miny-5*dy);
	TVertex<T> u(maxnbr+3,m_maxx-dx/2.0,m_maxy+10*dy);

	// adding to vertex list
	m_lVertices[ll.m_ID]=ll;
	m_lVertices[lr.m_ID]=lr;
	m_lVertices[u.m_ID]=u;

	m_triSuper=TTriangle<T>(&m_lVertices[ll.m_ID], &m_lVertices[lr.m_ID], &m_lVertices[u.m_ID]); 

	m_lFaces.push_front(m_triSuper); 
}

template<class T>
void TDelaunayMesher<T>::CleanSuperTriangles()
{
	// removing faces
	m_triSuper.PointOfTriangle(m_lFaces);
	// removing vertives
	RemoveVertex(m_triSuper.m_v0);	
	RemoveVertex(m_triSuper.m_v1);	
	RemoveVertex(m_triSuper.m_v2);	
}

template<class T>
bool TDelaunayMesher<T>::GenerateMesh()
{
	TTriangle<T> trianglej,t,tr2;
	TTriangle<T>::TriangleList lFacesIn, lFacesOut;
	TVertex<T>* pointj;
	bool help,help2;
	unsigned int nbtr;

	// clearing faces
	m_lFaces.clear();


	// first super triangle
	GenerateSuperTriangles();

	VertexContainer::iterator iVert;
	int count=0;
	for (iVert = m_lVertices.begin(); iVert != m_lVertices.end(); iVert++, count++)
	{		

		help = false;
		pointj = &(iVert->second);

		if ( m_triSuper.CommonPoint(pointj))
			continue;

		TTriangle<T> t;
		while ( !m_lFaces.empty() )
		{
			help2 = false;
			trianglej = m_lFaces.front();
			
			if (trianglej.InsideTriangle(pointj) && (!help) )
			{
				//a				
				t = trianglej;
				help = true;
				help2 = true;
				m_lFaces.pop_front();
			}

			if (!help2) 
			{ 
				
				if (trianglej.InsideTriangleCircumCircle(pointj)) 
				{//c
					lFacesIn.push_front(trianglej);
					m_lFaces.pop_front();
				}
				
				else
				{
					lFacesOut.push_front(trianglej);
					m_lFaces.pop_front();
				}
				
				// now we have treated all the triangles and we have two lists and a triangle t   
			}   
		}
		
		ASSERT(help);
		nbtr = lFacesIn.size();
		nbtr++;		
		if (nbtr == 1)
		{
			t.split1(pointj,lFacesIn);
		}			
		else if (nbtr == 2) 
		{
			tr2 = lFacesIn.front();
			lFacesIn.pop_front();
			t.split2(pointj,tr2,lFacesIn);
		}
		else
		{
			t.splitn( pointj, lFacesIn);
		}
				
		// Now we reactualise the list listtriangle with the new triangles. 		
		while (!lFacesIn.empty())
		{
			m_lFaces.push_front(lFacesIn.front());
			lFacesIn.pop_front();
		} 
		
		while (!lFacesOut.empty())
		{
			m_lFaces.push_front(lFacesOut.front());
			lFacesOut.pop_front();
		}
	}

	// Remove supertriangle
	CleanSuperTriangles();

	return true;
}


};

#endif // !defined(AFX_DELAUNAY_H__C909E909_83C7_4FC2_BCD1_04F48E889084__INCLUDED_)
